package service;

import org.apache.commons.lang.StringUtils;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.*;

public class FindCombinationService {
    // 输入 两个参数 1.字符串（文件路径），2. 整数
    // 文件内容是一堆数字，每一行是数字
//    1
//    1
//    -1
//    -2
//    -2
//    3
    // 1e56
    // 合法可以复制的内容值

    // 函数找出所有组合，他的和等于输入的整数
    // 输入直接打印组合 例如 1+2+3=6 -> 1，2，3  -> 1,1,1,2,2
    // 文件可大可小，路径可能不存在文件(fileNotExist)等等异常


    /**
     * 读取数据，排序后dfs
     *
     * @param dir
     * @param target
     */
    public void printCombination(String dir, int target) throws Exception {
        if (StringUtils.isBlank(dir)) throw new Exception("参数错误");
        try (BufferedReader bufferedReader = new BufferedReader(new FileReader(new File(dir)))) {
            List<Integer> valList = new ArrayList<Integer>();
            String curLine = null;
            while (null != (curLine = bufferedReader.readLine())) {
                valList.add(Integer.parseInt(curLine));
            }

            // 从小到大排序
            Collections.sort(valList);
            List<Integer> curCombination = new LinkedList<>();//便于递归
            dfs(valList, target, 0, curCombination);
        } catch (Exception e) {
            throw new Exception("运行时错误，请检查！\n" + e);
        }
    }

    /**
     * DFS循环遍历主方法
     *
     * @param valList
     * @param target
     * @param curPos
     * @param curCombination
     */
    public void dfs(List<Integer> valList, int target, int curPos, List<Integer> curCombination) {
        if (target == 0) {
            print(curCombination);
            return;
        }

        //选取当前值
        for (int i = curPos; i < valList.size(); i++) {
            if (target < valList.get(i)) break; //prune branches 做剪枝处理:valList已经升序排列，当前已经不满足条件，越往后累计更不满足条件了~~
            curCombination.add(valList.get(i));
            dfs(valList, target - valList.get(i), i + 1, curCombination);//此处原代码dfs传入下标为curPos，应该为i
            curCombination.remove(curCombination.size() - 1);   //此处原代码敲错了，敲成valList.size,run之后修正。
        }
    }

    /**
     * 负责打印数组的模块，可以自定义打印格式
     *
     * @param curCombination
     */
    public void print(List<Integer> curCombination) {
        //找到结果，打印
        // TODO:值得注意的是，结果集合会有重复，但题目没问清到底是否可以重复
        // TODO: 如果不允许重复，则最简单可以用set去重，也可以在dfs里跳过和上一个元素系统的curPos的值，以免重复
        for (Integer val : curCombination) {
            System.out.print(" " + val);
        }
        System.out.println("");
    }

    public static void main(String[] args) throws Exception {
        FindCombinationService findCombinationService = new FindCombinationService();
        findCombinationService.printCombination("/Users/vonmax/Downloads/input_02.txt", 8);
    }
}



